package com.peng.leetcode.tree;


/**
 * SortedListToBST
 *
 * @author: lupeng6
 * @create: 2021/4/20 15:48
 */
public class SortedListToBST {

    public static void main(String[] args) {

    }


    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    private TreeNode buildTree(ListNode l, ListNode r) {
        if (l == r) {
            return null;
        }
        ListNode mid = getMiddle(l, r);
        TreeNode node = new TreeNode(mid.val);
        node.left = buildTree(l, mid);
        node.right = buildTree(mid.next, r);

        return node;
    }


    private ListNode getMiddle(ListNode l, ListNode r) {
        ListNode low = l;
        ListNode fast = l;
        while (fast != r && fast.next != r) {
            fast = fast.next;
            fast = fast.next;
            low = low.next;
        }
        return low;
    }


    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }

        ListNode(int x, ListNode next) {
            val = x;
            this.next = next;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }
}



